package com.mashibing.class05;

/**
 * 异或(^)运算 : 等同于无进位相加.
 * 位与(&)运算 : 等同于有进位相加.
 */
// 测试链接：https://leetcode.com/problems/divide-two-integers
public class Code03_BitAddMinusMultiDiv {
    public static int add(int a, int b) {
        int sum = a;
        while (b != 0) { // 当b(进位信息)为0的时候,直接退出while循环
            sum = a ^ b; // 无进位相加信息 --> sum
            b = (a & b) << 1;   // 进位信息 --> b -> b'(进位信息)
            a = sum; // a -> a‘ 无进位信息
        }
        return sum;
    }

    // 求n的相反数, 就是对n进行取反加1
    public static int negNum(int n) {
        return add(~n, 1); // n取反加1
    }

    public static int minus(int a, int b) {
        return add(a, negNum(b)); // a + b的相反数
    }

    public static int multi(int a, int b) {
        int res = 0;
        while (b != 0) {
            if ((b & 1) != 0) { // (b & 1) != 0 说明b末尾存在1
                res = add(res, a);
            }
            a <<= 1;  // a 左移一位, 代表下一个1 比当前的1 要高一位.
            b >>>= 1; // b 每次向右移动一位
        }
        return res;
    }

    public static boolean isNeg(int n) {
        return n < 0;
    }

    public static int div(int a, int b) {
        // 得到x和y都是正数绝对值的形势.
        int x = isNeg(a) ? negNum(a) : a;
        int y = isNeg(b) ? negNum(b) : b;
        int res = 0;
        //i = minus(i, 1) 代表室i = i-1
        for (int i = 30; i >= 0; i = minus(i, 1)) {
            if ((x >> i) >= y) { // 检测x右移i位成立时,此时(x>>i)的值是大于y的最小值.
                res |= (1 << i); // 将res的第i位置1
                x = minus(x, y << i); // 将x的第i位置 与 y<<i 相减, 达到x位置0的效果.
            }
        }
        return isNeg(a) ^ isNeg(b) ? negNum(res) : res;
    }

    public static int divide(int a, int b) {
        if (a == Integer.MIN_VALUE && b == Integer.MIN_VALUE) { // a b 都是系统最小
            return 1;
        } else if (b == Integer.MIN_VALUE) {  // a不是系统最小 b是系统最小
            return 0;
        } else if (a == Integer.MIN_VALUE) { // a是系统最小 b不是系统最小
            if (b == negNum(1)) {
                return Integer.MAX_VALUE;
            } else {
                // 如果要计算a/b 就需要计算 (a+1)/b = c
                // a - (b*c) =d 看一下 a 与 b*c的值还差多少.
                // d /b =e
                // c + e
                int c = div(add(a, 1), b);
                return add(c, div(minus(a, multi(c, b)), b));
            }
        } else {
            return div(a, b);
        }
    }

    public static void main(String[] args) {
        Integer a = Integer.MIN_VALUE;
        System.out.println("a = " + a);
        a = -a;
        System.out.println("-a = " + a);
    }
}
